package algorithm.sort;

import algorithm.utils.Utils;
import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

  @Test
  public void test() {

//    int[] ints = Utils.RandomArr(10);
    this.arr = new int[]{92, 95, 100, 93, 99};
    System.out.println(Arrays.toString(this.arr));
    merge(0, 2, 4);
    System.out.println(Arrays.toString(this.arr));

    this.arr = Utils.RandomArr(20);

    System.out.println(Arrays.toString(this.arr));

    sort(0, this.arr.length - 1);

    System.out.println(Arrays.toString(this.arr));

  }

  public void sort(int low, int hight) {

    if (low >= hight) {
      return;
    }

    int mid = (hight + low) / 2;

    sort(low, mid);
    sort(mid + 1, hight);

    merge(low, mid, hight);

  }

  int[] arr;

  public void merge(int low, int mid, int high) {

    if (low >= high) return;

    //把（low,mid】 先单独拿出来 放到一个数组中,
    int[] lowmidArr = new int[mid - low + 1];

    for (int i = 0, lowCopy = low; i < mid - low + 1; i++, lowCopy++) {
      lowmidArr[i] = this.arr[lowCopy];
    }

    //开始并归了

    //声明两个指针
    int aArrIndex = 0;
    int bArrIndex = mid + 1;

    int curindex = low;
    while (aArrIndex < lowmidArr.length || bArrIndex <= high) {
//      if (aArrIndex >= lowmidArr.length && bArrIndex > high) {
//        break;
//      }

//      if (aArrIndex >= lowmidArr.length) {
//        this.arr[curindex++] = this.arr[bArrIndex++];
//      } else if (bArrIndex > high) {
//        this.arr[curindex++] = lowmidArr[aArrIndex++];
//      } else if (lowmidArr[aArrIndex] >= this.arr[bArrIndex]) {
//        this.arr[curindex++] = this.arr[bArrIndex++];
//      } else {
//        this.arr[curindex++] = lowmidArr[aArrIndex++];
//      }

      if (aArrIndex >= lowmidArr.length || (bArrIndex <= high && lowmidArr[aArrIndex] >= this.arr[bArrIndex])) {
        this.arr[curindex++] = this.arr[bArrIndex++];
      } else {
        this.arr[curindex++] = lowmidArr[aArrIndex++];
      }

    }

  }


}
